// 栅格遍历/着色问题
#include <stdio.h>

// 栅格数据在C语言中通常使用二维数组表示
// 多维数组作为函数参数：除了第一个维度不需要指定大小之外，后面必须指定大小
// 例如：func(int a[], int b[][5], int c[][3][4]){...}

// 1. 给定一个由0和1组成的二维网络，0和1分别代表海洋和岛屿，统计岛屿的个数，假设岛屿总是被海洋包围且仅水平和竖直方向的栅格才算相连
// 下列算法改变了原来的数据，若不允许改变原来的数据，则可以在参数中新增一个二维数组visit[][]，用于记录哪个格子被访问过

/// @brief 深度优先递归遍历统计岛屿个数
/// @param raster 原岛屿数据，为二维数组
/// @param rowSize 网络行数
/// @param colSize 网络列数
/// @param row 当前访问行
/// @param col 当前访问列
void rasterDFS(int raster[][5], int rowSize, int colSize, int row, int col)
{
	// 递归结束条件
	if (row < 0 || row >= rowSize || col < 0 || col >= colSize || raster[row][col] == 0)
	{
		return;
	}
	// 先访问当前网格，访问后标记为0
	raster[row][col] = 0;
	// 四向递归访问
	rasterDFS(raster, rowSize, colSize, row + 1, col);
	rasterDFS(raster, rowSize, colSize, row - 1, col);
	rasterDFS(raster, rowSize, colSize, row, col + 1);
	rasterDFS(raster, rowSize, colSize, row, col - 1);
}

/// @brief 使用深度优先遍历统计岛屿个数
/// @param raster 原岛屿数据，为二维数组
/// @param rowSize 网络行数
/// @param colSize 网络列数
/// @return 岛屿数量
int islandCountDFS(int raster[][5], int rowSize, int colSize)
{
	int i, j, count = 0;
	for (i = 0; i < rowSize; i++)
	{
		for (j = 0; j < colSize; j++)
		{
			if (raster[i][j] == 1)
			{
				rasterDFS(raster, rowSize, colSize, i, j);
				count++;
			}
		}
	}
	return count;
}

/// @brief 使用广度优先遍历统计岛屿个数
/// @param raster 岛屿网络数据
/// @param rowSize 网络行数
/// @param colSize 网络列数
/// @return 岛屿数量
int islandCountBFS(int raster[][5], int rowSize, int colSize)
{
	int i, j, count = 0;
	// 定义一个可以记录二维坐标的循环队列
	int max = 30, rear = 0, front = 0;
	struct
	{
		int row, col; // 二维坐标
	} queue[max], temp;
	// 先找到第一个不为0的点
	for (i = 0; i < rowSize; i++)
	{
		for (j = 0; j < colSize; j++)
		{
			// 这里进行广度优先遍历操作
			if (raster[i][j] == 1)
			{
				// 先访问并进队列
				raster[i][j] = 0;
				queue[rear].row = i;
				queue[rear].col = j;
				rear = (rear + 1) % max;
				while (rear != front)
				{
					// 出队列，并将其邻接的陆地网格访问并进队列
					temp = queue[front];
					front = (front + 1) % max;
					// 向上搜索
					if (temp.row - 1 >= 0 && raster[temp.row - 1][temp.col] == 1)
					{
						raster[temp.row - 1][temp.col] = 0;
						queue[rear].row = temp.row - 1;
						queue[rear].col = temp.col;
						rear = (rear + 1) % max;
					}
					// 向下搜索
					if (temp.row + 1 < rowSize && raster[temp.row + 1][temp.col] == 1)
					{
						raster[temp.row + 1][temp.col] = 0;
						queue[rear].row = temp.row + 1;
						queue[rear].col = temp.col;
						rear = (rear + 1) % max;
					}
					// 向左搜索
					if (temp.col - 1 >= 0 && raster[temp.row][temp.col - 1] == 1)
					{
						raster[temp.row][temp.col - 1] = 0;
						queue[rear].row = temp.row;
						queue[rear].col = temp.col - 1;
						rear = (rear + 1) % max;
					}
					// 向右搜索
					if (temp.col + 1 < colSize && raster[temp.row][temp.col + 1] == 1)
					{
						raster[temp.row][temp.col + 1] = 0;
						queue[rear].row = temp.row;
						queue[rear].col = temp.col + 1;
						rear = (rear + 1) % max;
					}
				}
				// 一趟访问完成，数量+1
				count++;
			}
		}
	}
	return count;
}

/// @brief 使用栈实现非递归的深度优先遍历以统计岛屿数量
/// @param raster 栅格网络数据
/// @param rowSize 网络行数
/// @param colSize 网络列数
/// @param row 访问起始行
/// @param col 访问起始列
void rasterStackTraverse(int raster[][5], int rowSize, int colSize, int row, int col)
{
	// 使用一个栈记录二维坐标
	int top = 0;
	struct
	{
		int row, col; // 格子行列数
	} stack[30], stackTop;
	// 起点入栈并标记
	stack[top].row = row;
	stack[top].col = col;
	top++;
	raster[row][col] = 0;
	// 查看栈顶元素并往四个方向探索，遇到死胡同出栈
	// 全部都出栈时说明这一连通区域已经遍历完成
	// 表示每次探索时下一个格子的行列，以及下一步是否可走
	// direct表示每次的探索方向，0-3表示上下左右，起始时为-1表示未探索过任何方向
	int nextRow, nextCol, findNext, direct;
	while (top != 0)
	{
		// 使用栈顶元素，栈顶元素表示当前所在的格子
		stackTop = stack[top - 1];
		// 四向探索
		findNext = 0;
		// 退栈也是要四个方向都探索，防止丢失方向
		for (direct = 0; direct < 4; direct++)
		{
			switch (direct)
			{
			case 0:
				nextRow = stackTop.row - 1;
				nextCol = stackTop.col;
				break;
			case 1:
				nextRow = stackTop.row + 1;
				nextCol = stackTop.col;
				break;
			case 2:
				nextRow = stackTop.row;
				nextCol = stackTop.col - 1;
				break;
			case 3:
				nextRow = stackTop.row;
				nextCol = stackTop.col + 1;
				break;
			}
			if (nextRow >= 0 && nextRow < rowSize && nextCol >= 0 && nextCol < colSize && raster[nextRow][nextCol] == 1)
			{
				// 访问并入栈
				raster[nextRow][nextCol] = 0;
				stack[top].row = nextRow;
				stack[top].col = nextCol;
				top++;
				findNext = 1;
				break;
			}
		}
		// 如果走到了死胡同（非陆地或者已访问），退栈一次然后重新搜索
		if (!findNext)
		{
			top--;
		}
	}
}

/// @brief 使用栈的深度优先遍历统计岛屿数量
/// @param raster 栅格网络
/// @param rowSize 网络行数
/// @param colSize 网络列数
/// @return 岛屿数量
int isLandCountStack(int raster[][5], int rowSize, int colSize)
{
	int i, j, count = 0;
	for (i = 0; i < rowSize; i++)
	{
		for (j = 0; j < colSize; j++)
		{
			if (raster[i][j] == 1)
			{
				rasterStackTraverse(raster, rowSize, colSize, i, j);
				count++;
			}
		}
	}
	return count;
}

// 2. 有一个10x10的二维矩阵表示一个岛屿的航拍地图，每个格子的数字表示海拔，0为海洋，1-9为陆地，编写程序计算降落地点的岛屿面积
// 思路和上面是一样的，只不过每次访问一个格子，把面积+1即可，这里不再提供代码

// 3. 有一副图像使用二维矩阵表示，每个格子不同的数值表示一种颜色，编写程序，将选取点所在的连通区域全部替换为另一个颜色
// 同样是两种遍历的思路，只是标记时换为指定数字的颜色即可，思路和上面基本上也是一样的

int main()
{
	// 示例数据
	int grid1[4][5] = {
		{1, 1, 0, 0, 0},
		{1, 1, 0, 0, 0},
		{0, 0, 1, 0, 0},
		{0, 0, 0, 1, 1}};
	int grid2[4][5] = {
		{1, 1, 1, 1, 0},
		{1, 1, 0, 1, 0},
		{1, 1, 0, 0, 0},
		{0, 0, 0, 0, 0}};
	int grid3[4][5] = {
		{1, 1, 0, 1, 0},
		{1, 1, 0, 1, 0},
		{1, 0, 1, 0, 0},
		{0, 0, 0, 0, 1}};
	printf("%d\n", islandCountDFS(grid1, 4, 5));
	printf("%d\n", islandCountBFS(grid2, 4, 5));
	printf("%d\n", isLandCountStack(grid3, 4, 5));
	return 0;
}